package com.whitedust.top50;

import com.whitedust.structure.ListNode;

import java.util.List;

/**
 * @author A
 * @since 2025/11/7 12:56
 */

public class Top47 {
    public ListNode sortList(ListNode head) {
        return partition(head);
    }

    private ListNode partition(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode head2 = midNode(head);
        // 分治
        head = partition(head);
        head2 = partition(head2);
        // 合并
        return sort2List(head, head2);
    }

    private ListNode midNode(ListNode head) {
        //不能使用哨兵记录会爆栈
        //因为当只有两个节点的时候会无线循环然后无法分割开
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //需要记录下中间节点的前一个节点并断开
        pre.next = null;
        return slow;
    }

    private ListNode sort2List(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 == null) {
            tmp.next = head2;
        } else {
            tmp.next = head1;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode d = new ListNode(1, null);
        ListNode c = new ListNode(3, d);
        ListNode b = new ListNode(2, c);
        ListNode a = new ListNode(4, b);
        ListNode node = new Top47().sortList(a);
        while (node != null) {
            System.out.println(node.val);
        }
    }
}
